While parallel processing offers significant advantages in the high speed processing of large volumes of information by routing and processing information on nodes of the system simultaneously, the processing can be deadlocked if some of the information is prevented from reaching its intended node or nodes preventing it from being applied with other information on the system or in proper sequence. This can happen if one or more of the internodal communication pathways that link the nodes of the parallel processing system are operating at capacity limiting the flow of information through them.
More particularly, during the processing of SQL statements by a shared-nothing, MPP (Massively Parallel Processor) database system, data must be moved between the computers (or nodes) that make up the database manager. The limited buffering available to communication lines connecting nodes combined with data skew between the nodes resulting from delayed information transmission between the nodes can result in a deadlock when the order of data records being processed must be preserved.
Previously these deadlocks were handled by changing the execution plan for the SQL statement. This requires developing techniques to recognize that a given plan may deadlock and then changing the plan to avoid the deadlock. In this approach the data processing plan is optimized by an SQL optimizer to generate the best performing plan, from the optimizer's viewpoint without taking into account the possibility of deadlocking, then changing the plan if necessary to avoid deadlocking.
As queries become more complex and SQL optimizers become more sophisticated, the detection of potential deadlocks becomes very difficult and the modified execution plan may not perform as efficiently as possible.
One reason behind the deadlocking problem is the limited in-memory buffering available to an internodal communication line. Theoretically this could be handled by increasing the number of communication buffers available, so that the database system can handle more extreme situations of data skew. Ultimately, by increasing the buffer size to a large enough size no deadlocks would occur. However, reality dictates limitations to buffer size.
While the problem of internodal deadlocking has been of concern since the advent of parallel processing systems it does not appear that a broadly applicable satisfactory solution to this problem has been found until the present invention was developed.